package com.liuyfly.utils;

import java.util.List;

/**
 * @author liuyangfang 2021/8/23 上午1:44
 */
public class SortUtil {
    /**
     * Suppresses default constructor, ensuring non-instantiability.
     */
    private SortUtil() {
    }

    public static <T extends Comparable<T>> void insertionSort(T[] array) {
        for (int i=1;i<array.length;i++) {


        }
    }

    /**
     * 选择排序
     * 
     * @param list 原始list
     */
    public static <T extends Comparable<T>> void selectionSort(List<T> list) {
        for (int i = 0; i < list.size(); i++) {
            int minObjectIndex = -1;
            T minObject = list.get(i);
            for (int j = i + 1; j < list.size(); j++) {
                if (list.get(j).compareTo(minObject) < 0) {
                    minObject = list.get(j);
                    minObjectIndex = j;
                }
            }
            if (minObjectIndex >= 0) {
                list.set(minObjectIndex, list.get(i));
                list.set(i, minObject);
            }
        }
    }

    /**
     * 选择排序
     * 
     * @param array 原始数组
     */
    public static <T extends Comparable<T>> void selectionSort(T[] array) {
        for (int i = 0; i < array.length; i++) {
            int minObjectIndex = -1;
            T minObject = array[i];
            for (int j = i + 1; j < array.length; j++) {
                if (array[j].compareTo(minObject) < 0) {
                    minObject = array[j];
                    minObjectIndex = j;
                }
            }
            if (minObjectIndex >= 0) {
                array[minObjectIndex] = array[i];
                array[i] = minObject;
            }
        }
    }

    /**
     * 冒泡排序算法
     * 
     * @param array 原始数组
     */
    public static <T extends Comparable<T>> void bubbleSort(T[] array) {
        int k;
        int flag = array.length;
        while (flag > 0) {
            k = flag;
            flag = 0;
            for (int j = 1; j < k; j++) {
                if (array[j - 1].compareTo(array[j]) > 0) {
                    T temp = array[j - 1];
                    array[j - 1] = array[j];
                    array[j] = temp;
                    flag = j;
                }
            }
        }
    }

    /**
     * 冒泡排序算法
     *
     * @param list 原始list
     */
    public static <T extends Comparable<T>> void bubbleSort(List<T> list) {
        int k;
        int flag = list.size();
        while (flag > 0) {
            k = flag;
            flag = 0;
            for (int j = 1; j < k; j++) {
                if (list.get(j - 1).compareTo(list.get(j)) > 0) {
                    T temp = list.get(j - 1);
                    list.set(j - 1, list.get(j));
                    list.set(j, temp);
                    flag = j;
                }
            }
        }
    }

    /**
     * 快速排序算法
     *
     * @param array 原始数组
     * @param low 低位
     * @param high 高位
     */
    public static <T extends Comparable<T>> void quickSort(T[] array, int low, int high) {
        int i, j;
        T temp, t;
        if (low > high) {
            return;
        }
        i = low;
        j = high;
        //temp为基准位元素
        temp = array[low];
        while (i < j) {
            //从右往左递减
            while (temp.compareTo(array[j]) <= 0 && i < j) {
                j--;
            }
            //从左往右递加
            while (temp.compareTo(array[i]) >= 0 && i < j) {
                i++;
            }
            //满足条件则交换
            if (i < j) {
                t = array[j];
                array[j] = array[i];
                array[i] = t;
            }
        }
        //最后将基准位元素与i和j相等位置的元素交换
        array[low] = array[i];
        array[i] = temp;
        //递归左半边数组
        quickSort(array, low, j - 1);
        //递归右半边数组
        quickSort(array, j + 1, high);
    }

    /**
     * 快速排序算法
     *
     * @param list 原始list
     * @param low 低位
     * @param high 高位
     */
    public static <T extends Comparable<T>> void quickSort(List<T> list, int low, int high) {
        int i, j;
        T temp, t;
        if (low > high) {
            return;
        }
        i = low;
        j = high;
        //temp为基准位元素
        temp = list.get(low);
        while (i < j) {
            //从右往左递减
            while (temp.compareTo(list.get(j)) <= 0 && i < j) {
                j--;
            }
            //从左往右递加
            while (temp.compareTo(list.get(i)) >= 0 && i < j) {
                i++;
            }
            //满足条件则交换
            if (i < j) {
                t = list.get(j);
                list.set(j, list.get(i));
                list.set(i, t);
            }
        }
        //最后将基准位元素与i和j相等位置的元素交换
        list.set(low, list.get(i));
        list.set(i, temp);
        //递归左半边数组
        quickSort(list, low, j - 1);
        //递归右半边数组
        quickSort(list, j + 1, high);
    }

}
